package edu.bupt.s1dp;

public class T15DistinctSubsequences {

    public int numDistinct(String s, String t) {
        if (s.length()==0 || t.length()==0)return 0;
        int[][] cache = new int[s.length()][t.length()];

        int tmp = 0;
        for (int i=0;i<s.length();i++){
            if (s.charAt(i) == t.charAt(0)){
                cache[i][0] = ++tmp;
            } else {
                cache[i][0] = tmp;
            }
        }

        for (int i=1;i<s.length();i++){
            for (int j=1;j<t.length() && j<s.length();j++){
                if (s.charAt(i) == t.charAt(j)){
                    cache[i][j] = cache[i-1][j] + cache[i-1][j-1];
                }else {
                    cache[i][j] = cache[i-1][j];
                }
            }
        }

        return cache[s.length()-1][t.length()-1];
    }

    public static void main(String[] args) {
        int i = new T15DistinctSubsequences().numDistinct("aabb", "ab");
    }
}
